#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
    public:
	int max_val(vector<int> &nums, int n)
	{
		if (n >= nums.size()) {
			return 0;
		}
		int val = max_val(nums, n + 1);
		int val2 = max_val(nums, n + 2) + nums[n];
		return max(val, val2);
	}

	int max_val(vector<int> &nums, int n, vector<int> &recd)
	{
		if (n >= nums.size()) {
			return 0;
		}
		if (recd[n] != -1) {
			return recd[n];
		}
		int val = max_val(nums, n + 1, recd);
		int val2 = max_val(nums, n + 2, recd) + nums[n];
		return recd[n] = max(val, val2);
	}

        int max_val_dp(vector<int> &nums)
        {
                vector<int> dp(nums.size(), 0);
                dp[0] = nums[0];
                dp[1] = max(nums[1], nums[0]);

                for(int i = 2; i < nums.size(); i++){
                        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
                }

                return dp.back();
        }

        int max_val_dp_sp(vector<int> &nums)
        {
                int prepre = nums[0];
                int pre = max(nums[0], nums[1]);

                int ans = pre;
                for(int i = 2; i < nums.size(); i++){
                        ans = max({pre, prepre + nums[i], nums[i]});
                        prepre = pre;
                        pre = ans;
                }

                return ans;
        }

	int rob(vector<int> &nums)
	{
		vector<int> recd(nums.size(), -1);
                if(nums.size() == 1){
                        return nums[0];
                }
		return max_val_dp_sp(nums);
	}
};

int main()
{
	vector<int> nums = { 114, 117, 207, 117, 235, 82,  90,	67,  143, 146, 53, 108, 200, 91, 80,  223, 58,	170, 110, 236, 81,  90,	 222, 160,
			     165, 195, 187, 199, 114, 235, 197, 187, 69,  129, 64, 214, 228, 78, 188, 67,  205, 94,  205, 169, 241, 202, 144, 240 };
	cout << Solution().rob(nums) << endl;
        
	return 0;
}